package cxydmmszl.chapter02.t012;

import java.util.Scanner;

/**
 * <li style="color: red;">Prob</li>
 * 打印两个有序链表的公共部分
 * <li style="color: red;">Desc</li>
 * 给定两个有序的链表的头指针 head1 和 head2，打印两个链表的公共部分。
 * <li style="color: red;">Link</li> CD48
 *
 * @author habitplus
 * @since 2021-08-27 21:00
 */
public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        Node head1 = inputAndGenList(sc);
        Node head2 = inputAndGenList(sc);

        Main test = new Main();
        test.printCommonPart(head1, head2);
    }

    public void printCommonPart(Node head1, Node head2) {
        StringBuilder sb = new StringBuilder();
        while (head1 != null && head2 != null) {
            if (head1.val > head2.val) {
                head2 = head2.next;
            } else if (head1.val < head2.val) {
                head1 = head1.next;
            } else {
                sb.append(head1.val).append(" ");
                head1 = head1.next;
                head2 = head2.next;
            }
        }
        System.out.println(sb.toString());
    }

    private static class Node {
        int val;

        Node next;
        public Node(int val) {
            this.val = val;
            this.next = null;
        }

    }

    private static Node inputAndGenList(Scanner sc) {
        int n = sc.nextInt();
        Node head = null, pre = null, node;
        int val;
        for (int i = 0; i < n; i++) {
            val = sc.nextInt();
            node = new Node(val);
            if (pre == null) {
                head = node;
                pre = head;
            } else {
                pre.next = node;
                pre = node;
            }
        }

        return head;
    }
}
